home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1991 / 04 / morrow / object.c < prev    next >
C/C++ Source or Header  |  1989-09-03  |  6KB  |  338 lines
  1. /***
  2. *       GASystem
  3. *       Mike Morrow
  4. *       September 1989
  5. ***/
  6.  
  7.  
  8. /**
  9. *    Objective function.  Evaluates a set of directions as applied to a
  10. *    maze.  The closer the set of directions gets to the end of the
  11. *    maze, the higher the fitness of that set of directions.
  12. **/
  13.  
  14.  
  15.  
  16. #include "ga.h"
  17. #include <stdio.h>
  18.  
  19.  
  20. /**
  21. *    A set of directions is made up of the following.
  22. **/
  23. #define NORTH   0
  24. #define    EAST    1
  25. #define WEST    2
  26. #define SOUTH    3
  27.  
  28.  
  29. /**
  30. *    Define the maze
  31. **/
  32.  
  33. #if MSDOS
  34. #define BLOCK    (char) 178        /* block char on PC */
  35. #define SPACE    ' '
  36. #else
  37. #define BLOCK    '@'
  38. #define SPACE    ' '
  39. #endif
  40.  
  41. #define    _            BLOCK,
  42. #define A            SPACE,
  43.  
  44. #define    MAZEX    17
  45. #define MAZEY    13
  46.  
  47. typedef char MAZE[MAZEY][MAZEX];
  48. typedef char DISPLINE[80];
  49.  
  50. static CONST MAZE maze =
  51. {
  52.     _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
  53.     _ A A A A A A A _ _ _ _ _ _ _ A _
  54.     _ A _ _ A _ _ _ _ _ A A _ _ _ A _
  55.     _ A _ _ A A A A A A A _ _ A A A _
  56.     _ A _ _ A _ _ _ A _ _ _ _ A _ _ _
  57.     _ A _ _ _ _ _ _ A A A _ _ A _ A _
  58.     _ A _ _ A _ _ _ _ _ _ _ _ A _ A _
  59.     _ A A A A A A _ _ _ A A A A _ A _
  60.     _ _ _ _ A _ _ _ A _ A _ _ A _ A _
  61.     _ A _ _ A _ A A A _ A A _ A A A _
  62.     _ A A A A _ _ _ A _ _ _ _ _ _ A _
  63.     _ A _ _ A A A A A A A A A A A A _
  64.     _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
  65. };
  66.  
  67. /**
  68. *    Maze runners start at this point in the maze.
  69. **/
  70. #define MAZESTARTX    10
  71. #define MAZESTARTY    11
  72.  
  73. /**
  74. *    Maze runners' goal is this point in the maze.
  75. **/
  76. #define MAZEENDX    7
  77. #define MAZEENDY    1
  78.  
  79. /**
  80. *    How far from the MAZEEND is this set of points (x, y)?
  81. **/
  82. #define DIST(x, y) ((MAZEENDX - x) * (MAZEENDX - x) + (MAZEENDY - y) * (MAZEENDY - y))
  83.  
  84. /**
  85. *    What is the longest distance in a maze this size?
  86. **/
  87. #define MAXDIST ((MAZEX * MAZEX) + (MAZEY * MAZEY))
  88.  
  89.  
  90.  
  91.  
  92. #if __STDC__ || __ZTC__
  93. static int mazerun(SEQ s, int len, unsigned int *xp, unsigned int *yp);
  94. static int xroads(int x, int y);
  95. #else
  96. static int mazerun();
  97. static int xroads();
  98. #endif
  99.  
  100. void objinit()
  101. {
  102.     char exebuff[80];
  103.     
  104.     /**
  105.     *    set parameters.  High allele should be SOUTH, low allele
  106.     *    should be NORTH.
  107.     **/
  108.     sprintf(exebuff, "HIA = %d", SOUTH);
  109.     exec(exebuff);
  110.  
  111.     sprintf(exebuff, "LOWA = %d", NORTH);
  112.     exec(exebuff);
  113.  
  114.  
  115.         /**
  116.         *       For starters, give a gene this many elements.
  117.         *       The user may want to experiment with this parameter
  118.         *       anyway.
  119.         **/
  120.     sprintf(exebuff, "LEN = 15");
  121.     exec(exebuff);
  122. }
  123.  
  124.  
  125.  
  126. /***
  127. **    This function evaluates a gene's sequence of directions.  It returns
  128. **    a fitness value.
  129. ***/
  130. FIT_TYPE objective(s, len)
  131. SEQ s;
  132. int len;
  133. {
  134.     FIT_TYPE dist;
  135.     unsigned int x, y;
  136.     int n_moves;
  137.  
  138.     /**
  139.     *    Run through the maze using the directions in s.  x and y will get
  140.     *    the final position we reach.  n_moves will get the number of moves it
  141.     *    took to get there.
  142.     **/
  143.     n_moves = mazerun(s, len, &x, &y);
  144.     
  145.     /**
  146.     *    The fitness of that path through the maze is the
  147.     *    distance from the MAZEEND.
  148.     **/
  149.     dist = DIST(x, y);
  150.     
  151.     /**
  152.     *    Convert: lower distances imply higher fitness value.
  153.     **/
  154.     dist = (FIT_TYPE)MAXDIST - dist;
  155.     
  156.     
  157.     /**
  158.     *    Scale down result.
  159.     **/
  160.     dist = (dist * dist) >> 12;
  161.     
  162.     
  163.     /**
  164.     *    Plus a bonus for brevity.
  165.     **/
  166.     dist += 5 * (FIT_TYPE) (len - n_moves);
  167.  
  168.     return dist;
  169. }
  170.  
  171.  
  172. static CONST char i_to_c[] = "NEWS";
  173.  
  174.  
  175. #define N_PER_DISP_BLOCK    5
  176.  
  177. static DISPLINE displines[N_PER_DISP_BLOCK];
  178. static int n_lines = 0;
  179. static MAZE disp_maze;
  180.  
  181. void objshow(s, len, fitness)
  182. SEQ s;
  183. int len;
  184. FIT_TYPE fitness;
  185. {
  186.     unsigned int x, y;
  187.     int n_moves;
  188.     DISPLINE buff;
  189.     
  190.     if(! n_lines)
  191.         memcpy(disp_maze, maze, sizeof maze);
  192.         
  193.         
  194.     n_moves = mazerun(s, len, &x, &y);
  195.     
  196.     disp_maze[y][x] = '0' + n_lines;
  197.     
  198.     sprintf(displines[n_lines], "%6d    ", fitness);
  199.     while(len--)
  200.     {
  201.         if(*s > SOUTH)
  202.             sprintf(buff, " %d!", *s++);
  203.         else
  204.             sprintf(buff, " %c", i_to_c[*s++]);
  205.         strcat(displines[n_lines], buff);
  206.     }
  207.  
  208.     sprintf(buff, " : (%2d, %2d); %2d moves", x, y, n_moves);
  209.     strcat(displines[n_lines], buff);
  210.     
  211.     n_lines++;
  212.     if(n_lines == N_PER_DISP_BLOCK)
  213.         objdumpdone();
  214. }
  215.  
  216.  
  217.  
  218. void objdumpdone()
  219. {
  220.     unsigned int i, x, y;
  221.     
  222.     if(! n_lines)
  223.         return ;
  224.     
  225.     for(i = 0; i < n_lines; i++)
  226.     {
  227.         printf("%d)    %s\n", i, displines[i]);
  228.     }
  229.     
  230.     puts("");
  231.     for(y = 0; y < MAZEY; y++)
  232.     {
  233.         printf("        ");
  234.         for(x = 0; x < MAZEX; x++)
  235.         {
  236.                 putchar(disp_maze[y][x]);
  237.         }
  238.         puts("");
  239.     }
  240.     n_lines = 0;
  241.     puts("\n\n");
  242. }
  243.  
  244.  
  245.  
  246.  
  247.  
  248. /**
  249. *    Run through the maze with the directions given in s.  *xp and *yp are set
  250. *    to the final coords that we end up with.
  251. *    This function returns the number of moves it took to run the maze.
  252. *    It will terminate when the moves in s are used up, or when we
  253. *    arrive at the end of the maze.
  254. **/
  255. static int mazerun(s, len, xp, yp)
  256. SEQ s;
  257. int len;
  258. unsigned int *xp, *yp;
  259. {
  260.     register int x, y;
  261.     register SEQ dirs;
  262.     int n_moves;
  263.  
  264.     
  265.     x = MAZESTARTX;
  266.     y = MAZESTARTY;
  267.     dirs = s;
  268.     n_moves = 0;
  269.     
  270.         while(len-- && ! (x == MAZEENDX && y == MAZEENDY))
  271.         {
  272.                 switch(*dirs++)
  273.                 {
  274.                         case NORTH:
  275.                              while(maze[y - 1][x] == SPACE)
  276.                              {
  277.                                 y--;
  278.                                 if(xroads(x, y))
  279.                                 break;
  280.                               }
  281.                          break;
  282.                 
  283.             case EAST:
  284.                 while(maze[y][x + 1] == SPACE)
  285.                 {
  286.                     x++;
  287.                     if(xroads(x, y))
  288.                         break;
  289.                 }    
  290.                 break;
  291.                 
  292.             case WEST:
  293.                 while(maze[y][x - 1] == SPACE)
  294.                 {
  295.                     x--;
  296.                     if(xroads(x, y))
  297.                         break;
  298.                 }    
  299.                 break;
  300.                 
  301.             case SOUTH:
  302.                 while(maze[y + 1][x] == SPACE)
  303.                 {
  304.                     y++;
  305.                     if(xroads(x, y))
  306.                         break;
  307.                 }
  308.                 break;
  309.                 
  310.             default:
  311.                 printf("Error in objective(), got allele = %d!", *(dirs - 1));
  312.                 break;
  313.         }
  314.         n_moves++;
  315.     }
  316.     *xp = x;
  317.     *yp = y;
  318.     
  319.     return n_moves;
  320. }
  321.  
  322.  
  323.  
  324. /**
  325. *    If this is a cross roads in the maze, i.e. there are more than two exits
  326. *    from the current cell, then return TRUE.
  327. **/
  328. static int xroads(x, y)
  329. int x, y;
  330. {
  331.     char exits;
  332.     
  333.     exits = (maze[y][x+1] != SPACE) + (maze[y][x-1] != SPACE) +
  334.         (maze[y+1][x] != SPACE) + (maze[y-1][x] != SPACE);
  335.     return exits < 2;
  336. }
  337.  
  338.